from typing import List


class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        s1 = len(s)
        s2 = len(p)

        left, right = 0, len(removable)
        while left < right:
            mid = (left + right + 1) // 2
            remove = set(removable[:mid])

            j = 0
            for i in range(s1):
                if s[i] == p[j] and i not in remove:
                    j += 1
                if j == s2:
                    break

            if j == s2:  # 还是子序列
                left = mid
            else:  # 不是子序列的了
                right = mid - 1

        return left


if __name__ == "__main__":
    print(Solution().maximumRemovals(s="abcacb", p="ab", removable=[3, 1, 0]))  # 2
    print(Solution().maximumRemovals(s="abcbddddd", p="abcd", removable=[3, 2, 1, 4, 5, 6]))  # 1
    print(Solution().maximumRemovals(s="abcab", p="abc", removable=[0, 1, 2, 3, 4]))  # 0

    # 自制用例
    print(Solution().maximumRemovals(s="abcacb", p="ab", removable=[3, 1, 4]))  # 3
